1. Field of the Invention
This invention relates generally to communication networks and, more particularly, to routing algorithms for ad-hoc networks, such as, for example, a multi-hop or a low rate-wireless personal area network (LR-WPAN). The invention also relates to methods of routing communications in a communication network, such as an ad-hoc network.
2. Background Information
Wireless networks are an emerging new technology, which allows users to access information and services electronically, regardless of their geographic position. Wireless networks may be classified in two types: (1) infra-structured networks; and (2) infra-structureless (or ad-hoc) networks. Every ad-hoc network is infra-structureless, but the opposite is not true. A main characteristic of ad-hoc networks is self-configuration.
An infra-structured network includes a communication network with fixed and wired gateways. A mobile unit or host communicates with a bridge in the network (called a base station) within its communication radius. The mobile host can move geographically while it is communicating. When it goes out of range of one base station, it connects with a new base station and starts communicating through it. This is called handoff. In this approach, the base stations are fixed.
In contrast to infra-structured networks, all nodes in ad-hoc networks are potentially mobile and can be connected dynamically in an arbitrary manner. All nodes of these networks behave as routers and take part in discovery and maintenance of routes to other nodes in the network. For example, ad-hoc networks are very useful in emergency search-and-rescue operations, meetings or conventions in which persons wish to quickly share information, and in data acquisition operations in inhospitable terrains.
An ad-hoc mobile communication network comprises a plurality of mobile hosts, each of which is able to communicate with its neighboring mobile hosts, which are a single hop away. In such a network, each mobile host acts as a router forwarding packets of information from one mobile host to another.
In an ad-hoc mobile communication network, the mobile hosts communicate with each other over a wireless media without any infra-structured (or wired) network component support. Accordingly, one of the most important features of any routing method or protocol for an ad-hoc mobile communication network is the ability to adapt well to link changes, namely changes in the interconnectivity between mobile hosts due to mobile hosts' migrations. Ideally, mobile hosts should not spend most of their time updating and computing routes in sympathy with other mobile hosts' movements. However, conventional distributed routing schemes attempt to maintain consistent routing information by performing periodic link and topology updates. These updates are undesirable because of the frequent link changes occurring in ad-hoc mobile communication networks, which can result in an enormous number of transmissions over the wireless media to propagate and update routes. This is highly impractical, very inefficient and results in low data throughput in an environment where bandwidth and battery power are scarce resources.
Several ad-hoc mobile routing schemes have evolved over the past few years. Most of these schemes are based on either broadcast or point-to-point routing using either the connectionless or connection-oriented packed forwarding approach. Routing protocols for ad-hoc networks can be divided into two categories: (1) table-driven; and; (2) on-demand. In a table-driven routing protocol, all up-to-date routes are maintained in every node. In an on-demand routing protocol, the routes are only created as and when required. When a source wants to send to a destination, it invokes a route discovery mechanism to find the path to the destination. The route remains valid until the destination is reachable or until the route is no longer needed.
One type of on-demand ad-hoc routing protocol is Dynamic Source Routing (DSR). A conventional DSR network enables communications between any devices in such network by discovering communication routes to other devices in the network. See, for example, Johnson et al., “Dynamic Source Routing in Ad Hoc Wireless Networks”, Mobile Computing, 1996. Dynamic Source Routing for mobile communication networks avoids periodic route advertisements because route caches are used to store source routes that a mobile host has learned over time. A combination of point-to-point and broadcast routing using the connection-oriented packet forwarding approach is used. Routes are source-initiated and discovered via a route discovery protocol. With source routing, the sender explicitly lists the route in each packet's header, so that the next-hop nodes are identified as the packet travels towards the destination. Cached route information is used and accurate updates of these route caches are essential, otherwise routing loops can occur. Since the sender has to be notified each time a route is truncated, the route maintenance phase does not support fast route reconstruction. See, also, U.S. Pat. Nos. 6,167,025; 6,034,961; and 5,987,011.
The DSR protocol appends a complete list of addresses from one peer device to another peer device for communications. That is, each device in a DSR network knows the entire path to another device, although this stored path may dynamically change.
The two major phases of the DSR protocol are: (1) route discovery; and (2) route maintenance. When a source node wants to send a packet to a destination node, it looks up its route cache to determine if it already contains a route to the destination. If it finds that an un-expired route to the destination exists, then it uses this route to send the packet. However, if the source node does not have such a route, then it initiates the route discovery process by broadcasting a route request packet. The route request packet contains the address of the source and the destination, and a unique identification number. The route request packet is sent from the source node to the destination through intermediate nodes on several different paths. Each intermediate node checks whether it knows of a route to the destination. If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbors. To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and its address is not present in the route record of the packet.
A route reply is generated when either the destination or an intermediate node with current information about the destination receives the route request packet. A route request packet reaching such a node already contains, in its route record, the sequence of hops taken from the source to this node. As the route request packet propagates through the network, a route record is formed. If the route reply is generated by the destination, then it places the route record from the route request packet into the route reply packet. On the other hand, if the node generating the route reply is an intermediate node, then it appends its cache route to destination to the route record of the route request packet and puts that into the route reply packet. To send the route reply packet, the responding node must have a route to the source. If it has a route to the source in its route cache, it can use that route. The reverse of route record can be used if symmetric links are supported. In case symmetric links are not supported, the node can initiate route discovery to source and piggyback the route reply on this new route request.
The DSR protocol uses two types of packets for route maintenance: (1) a route error packet; and (2) acknowledgements. When a node encounters a fatal transmission problem at its data link layer, it generates a route error packet. When a node receives a route error packet, it removes a hop-in-error from its route cache. All routes that contain the hop-in-error are truncated at that point. Acknowledgement packets are used to verify the correct operation of the route links. This also includes passive acknowledgements in which a node hears the next hop forwarding the packet along the route.
A DSR algorithm, which is employed in ad-hoc networking communication mobile networks, is relatively very simple, albeit highly inefficient. This is because redundant information is passed along several paths, thereby wasting communication bandwidth and battery power of the nodes. In addition, DSR requires that the information paths be bidirectional, in order that they can carry both route request packets and route replies. Still further, DSR requires that the cache in each node store the preferred communication routes for both upstream and downstream communications. Hence, each device in the DSR network must be capable of storing within the entire route to a destination, regardless how many devices the message must pass through.
Although DSR is one of the simplest algorithms, it has the disadvantage of using relatively very long “packets”. Anything that uses “Source Routing” has this disadvantage.
There exists the need to simplify the installation of communication networks.
There is the need to simplify the deployment of ad-hoc communication networks.
There is room for improvement in wired and wireless communication networks and systems.
There is also room for improvement in ad-hoc networks and in methods of routing communications in ad-hoc networks.